# https://leetcode.cn/problems/numbers-with-repeated-digits/description/
# 1012. 至少有 1 位重复的数字
# medium, 刘小康 2024.09.26
# 数位DP

class Solution:
    def before_k(self, k: int) -> int:  # DEBUG
        if k == 0:
            return 0
        if k == 1:
            return 9
        if k > 1:
            ans = 9
            flag = 9
            for i in range(k - 1):
                ans *= flag
                flag -= 1
            return ans + self.before_k(k - 1)

    def after_k(self, num: str) -> int:
        used_number = [False for _ in range(10)]
        dp = [[0, 0] for _ in range(len(num))]
        dp[0][0] = int(num[0]) - 1
        dp[0][1] = 1
        print(0, dp[0])
        used_number[int(num[0])] = True
        flag = 9
        for i in range(1, len(num)):
            if used_number[int(num[i])] is False:
                dp[i][1] = dp[i - 1][1]
            used_number[int(num[i])] = True
            dp[i][0] += dp[i - 1][0] * flag
            flag -= 1
            for j in range(len(used_number)):
                if j == int(num[i]):
                    break
                if j < int(num[i]) and used_number[j] is False:
                    dp[i][0] += dp[i - 1][1]
            print(i, dp[i])

        return sum(dp[len(num) - 1])

    def countSpecialNumbers(self, n: int) -> int:
        num_s = str(n)
        ans = self.before_k(len(num_s) - 1)

        return ans + self.after_k(num_s)

    def numDupDigitsAtMostN(self, n: int) -> int:
        return n - self.countSpecialNumbers(n)
